import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class PrimeFactorsCalculator {

    private Set<Long> primes;
    private List<Long> factors;

    {
        primes = new HashSet<>();
        primes.add(2L);
        primes.add(3L);

        factors = new ArrayList<>();
    }

    List<Long> calculatePrimeFactorsOf(Long inputNumber) {
        if (inputNumber <= 1) {
            return Collections.emptyList();
        }

        if (inputNumber == 2) {
            return Collections.singletonList(2L);
        }

        if (inputNumber == 3) {
            return Collections.singletonList(3L);
        }

        this.calculatePrimes(inputNumber);
        this.calculateFactors(inputNumber);

        return this.factors;
    }

    void calculateFactors(Long inputNumber) {
        if (inputNumber == 1) {
            return;
        }

        for (Long prime : this.primes) {
            if (inputNumber % prime == 0) {
                this.factors.add(prime);
                this.calculateFactors(inputNumber / prime);
                break;
            }
        }
    }

    void calculatePrimes(final Long inputNumber) {
        Long halfInputNumber = (long) Math.sqrt((double) inputNumber);
//        Long halfInputNumber = inputNumber / 2 + 1L;
        for (long i = 5; i < halfInputNumber; ) {
            boolean isPrime = true;
            for (Long prime : this.primes) {
                if (i % prime == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) this.primes.add(i);

            i = i + 2;
        }
    }

}